package com.liunian.algorithmstudy.str.kmp;

public class RepeatedSubstringPattern {

    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int[] next = new int[n];
        getNext(chars, next);
        if (next[n - 1] > 0 && n % (n - next[n - 1]) == 0) {
            return true;
        }
        return false;
    }

    private void getNext(char[] chars, int[] next) {
        int j = 0;
        for (int i = 1; i < chars.length; i++) {
            while (j > 0 && chars[i] != chars[j]) {
                j = next[j - 1];
            }
            if (chars[i] == chars[j]) {
                j++;
            }
            next[i] = j;
        }
    }

    public static void main(String[] args) {
        RepeatedSubstringPattern pattern = new RepeatedSubstringPattern();
        System.out.println(pattern.repeatedSubstringPattern("abac"));
    }

}
